class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    void dfs(int k, int n, vector<int>& nums, vector<int>& temp){
        if(n == temp.size()) {ans.emplace_back(temp); return;}
        else if(k>=nums.size()) return;
        for(int i=k; i<nums.size(); ++i){
            temp.push_back(nums[i]);
            dfs(i+1, n, nums, temp);
            temp.pop_back();
            while(i+1<nums.size() && nums[i]==nums[i+1]) ++i;
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i=0; i<=nums.size(); ++i){
            dfs(0, i, nums, temp);
        }
        return ans;
    }
};